package Hot100;

import common.TreeNode;

/**
 * @author zhangmin
 * @create 2021-12-27 10:08
 */
public class buildTree105 {
    /**105. 从前序与中序遍历序列构造二叉树
     * 给定一棵树的前序遍历 preorder 与中序遍历  inorder。请构造二叉树并返回其根节点。
     * 递归，依据前序遍历第一个节点值，在中序遍历中确定左右子树的范围和长度，递归调用构建子树
     * */
    TreeNode build(int[] preorder,int[] inorder,int pre_start,int pre_end,int in_start,int in_end){
        if (pre_start<0||pre_end>=preorder.length||pre_start>pre_end||in_start<0||in_end>inorder.length||in_start>in_end) return null;
        int rootNum=preorder[pre_start];
        TreeNode root=new TreeNode(rootNum);
        //在中序遍历中找到root的位置
        int i = in_start;
        for (; i <=in_end ; i++) {
            if (inorder[i]==rootNum) break;
        }
        int leftlen=i-in_start;
        //前序遍历中：root，左子树[pre_start+1,pre_start+leftlen],右子树[pre_start+leftlen+1,pre_end]
        //中序遍历中：左子树[in_start,i-1],root，右子树[i+1,in_end]
        root.left=build(preorder,inorder,pre_start+1,pre_start+leftlen,in_start,i-1);
        root.right=build(preorder,inorder,pre_start+leftlen+1,pre_end,i+1,in_end);
        return root;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(preorder,inorder,0,preorder.length-1,0,inorder.length-1);
    }
}
